package com.bascker.algorithm.common.util;

import com.bascker.algorithm.base.linkedlist.ListNode;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class ListUtil {

    /**
     * remove the element which find first in list
     *
     * @param head    list
     * @param element the element which want to be delete
     * @param <T>     node type
     * @return the list
     */
    public static <T> ListNode<T> remove(final ListNode<T> head, final T element) {
        ListNode<T> sentinel = new ListNode<>();
        sentinel.setNext(head);

        ListNode<T> pre = sentinel;
        ListNode<T> cur = head;
        while (Objects.nonNull(cur)) {
            if (cur.getItem().equals(element)) {
                pre.setNext(cur.getNext());
                break;
            } else {
                pre = cur;
            }

            cur = cur.getNext();
        }

        return sentinel.getNext();
    }

    /**
     * remove the tail node
     *
     * @param <T> Node Type
     * @return Map
     * key1: list,    value1: the list after remove tail node
     * key2: tailVal, value2: the tail node value
     */
    public static <T> Map<String, Object> removeTail(final ListNode<T> head) {
        final String KEY_LIST = "list";
        final String KEY_TAIL_VAL = "tailVal";

        if (Objects.isNull(head)) {
            return new HashMap<String, Object>() {
                {
                    put(KEY_LIST, null);
                    put(KEY_TAIL_VAL, null);
                }
            };
        }


        final ListNode<T> sentinel = new ListNode<>();
        sentinel.setNext(head);

        ListNode<T> pre = sentinel;
        ListNode<T> tail = head;
        while (Objects.nonNull(tail.getNext())) {
            pre = pre.getNext();
            tail = tail.getNext();
        }

        final T val = tail.getItem();
        pre.setNext(null);
        return new HashMap<String, Object>() {
            {
                put(KEY_LIST, sentinel.getNext());
                put(KEY_TAIL_VAL, val);
            }
        };
    }

    /**
     * remove the k th element
     *
     * @param head list
     * @param k    index
     * @param <T>  node type
     */
    public static <T> ListNode<T> removeKth(final ListNode<T> head, final int k) {
        final ListNode<T> sentinel = new ListNode<>();
        sentinel.setNext(head);

        ListNode<T> pre = sentinel;
        ListNode<T> cur = head;

        int len = 0;
        while (Objects.nonNull(cur)) {
            len++;
            if (len == k) {
                break;
            }

            pre = pre.getNext();
            cur = cur.getNext();
        }

        if (len == k) {
            pre.setNext(cur.getNext());
            cur.setNext(null);
        }


        return sentinel.getNext();
    }

    /**
     * Does the key in list?
     *
     * @param head list
     * @param key  target element
     * @param <T>  node type
     * @return true or false
     */
    public static <T> boolean find(final ListNode<T> head, final T key) {
        boolean rs = false;

        ListNode<T> cur = head;
        while (Objects.nonNull(cur)) {
            if (Objects.equals(cur.getItem(), key)) {
                rs = true;
                break;
            }

            cur = cur.getNext();
        }

        return rs;
    }

}
